package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 在一个 m * n 的二维数组中搜索是否存在某个元素。在数组中的数字从左至右已排列好，每行的第一个数字都大于上一行的最后一个数字
 * 实例1:
 * 输入:
 * matrix = [
 * [1, 3, 5, 7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * target = 3
 * 输出: true
 * <p>
 * 实例2:
 * 输入:
 * matrix = [
 * [1, 3, 5, 7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * target = 13
 * 输出: false
 * <p>
 * 思路：
 * 进行两次2分法
 *
 * @author hanxinghua
 * @create 2024/1/23
 * @since 1.0.0
 */
public class No74SearchMatrix {

    public static void main(String[] args) {

        /**
         * 矩阵
         */
        int[][] matrix = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 50}
        };

        System.out.println(method1(matrix, 13));

    }


    /**
     * 方法1
     * <p>
     * 使用两次2分法
     *
     * @param matrix
     * @param target
     * @return
     */
    private static Boolean method1(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        // 二分法查找 目标数在那行
        int low = 0, high = matrix.length - 1, mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (target == matrix[mid][0]) {
                return true;
            } else if (target > matrix[mid][0]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // 使用low，确认数据可能在那行
        int index = 0;
        if (target > matrix[low][0]) {
            index = low;
        } else {
            index = low - 1;
        }

        // 去具体行上找该数据
        int left = 0, right = matrix[index].length - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == matrix[index][mid]) {
                return true;
            } else if (target > matrix[index][mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

}
